P5468 [NOI2019] 回家路线
斜率优化入门（指我写的东西而不是这道题）
题意
\(n\) 个节点，有 \(m\) 趟列车，车 \(i\) 从 \(p_i\) 时刻至 \(q_i\) 时刻从 \(x_i\) 地到 \(y_i\) 地。猫猫需要只坐列车从 \(1\) 节点到达 \(n\) 节点。
设猫猫在一个地方等待的时间为 \(t\)，那么代价为 \(At^2+Bt+C\)，其中 \(A\ B\ C\) 为给定非负常数，总代价为所有代价总和与到达时间的和。求最小代价。
思路
设 \(f_i\) 为走 \(i\) 趟列车前的最小代价，有转移方程： \[ f_i=\min_{y_j=x_i\land q_j\leq q_i}(f_j+A(p_i-q_j)^2+B(p_i-q_j)+C) \] 最终代价即为： \[ \min f_i+q_i \] 对于第一个方程，不考虑其他限制，即为找到最优的 \(j\) 更新 \(i\)，有： \[ \begin{aligned} f_i&=f_j+A(p_i-q_j)^2+B(p_i-q_j)+C\\ f_i&=f_j+Ap_i^2+Aq_j^2-2Ap_iq_j+Bp_i-Bq_j+C\\ f_j+Aq_j^2-Bq_j&=2Ap_iq_j+f_i-Ap_i^2-Bp_i-C \end{aligned} \] 对于已经更新过的 \(j\)，\(f_j+Aq_j^2-Bq_j\) 是已知的。后半部分 \(f_i-Ap_i^2-Bp_i-C\) 只有 \(f_i\) 是未知的，也是我们要最优化的。
那么我们可以将上式看做 \(y=kx+b\) 的形式，其中 \[ \begin{aligned} &y=f_j+Aq_j^2-Bq_j\\ &x=q_j\\ &k=2Ap_i\\ &b=f_i-Ap_i^2-Bp_i-C \end{aligned} \] （常数其实可以属于任意一个位置，上述只是举例）
那么我们可以将所有可以转移到的 \(j\) 看做一个二维平面上的点，每次更新 \(f_i\) 实际是对一个斜率找出经过其中一个点得到的最优的 \(b\)。那么显然只会选到前者构成的凸包上的点。很多题查询的斜率都是单调的，而且之后在凸包后方插入新的点，于是维护凸包的数组就变成了单调队列。否则的话，就是动态维护凸包并在凸包上二分。
对于这道题，最优指最小，那么我们维护的是下凸包。
斜率优化的部分已经完了。考虑加入 \(y_j=x_i, q_j\leq p_i\) 的限制怎么做。对于第一个限制，发现不同点互不影响，那么我们对每个点开一个单调队列，对于一个列车在它的 \(x\) 位置查询就好了。对于第二个限制，我们将所有列车按照 \(p\) 排序然后枚举时间，那么对于上面更新完的列车先不插入队列，当枚举时间到 \(p\) 的时候再将其插入即可。这样就能满足所有限制，并且保证查询的斜率单调递增。
代码
好像不会炸 long long 的样子。
1 |
|
